<html>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1255">
</head>
<body>
<h2>Recursive computations and Memoization</h2>

In this column, I will present the technique of Memoization (or caching) to speed up
recursive computations. 

<h3>Recursion</h3>

In mathematics and computer science, recursion is a way of specifying 
something (usually a mathematical object or part of a computer program) 
by reference to itself. More precisely (and to dispel the appearance of 
circularity in the definition), "complicated" instances are defined in 
terms of "simpler" instances, and the "simplest" instances are given 
explicitly.
<p>
One interesting "application" of recursion is the definition of the set
of natural numbers. We can define a natural number recursively as follows:
<ul type="disc">
	<li>0 is natural</li>
	<li>If <i>n</i> is natural, then <i>n + 1</i> is also natural</li>
</ul>
So, 0 is natural by definition. 1 is natural, because 0 is natural and 1 = 0 + 1. 2 is 
natural because 2 = 1 + 1 and 1 is natural, and so on.

<h3>Fibonacci numbers</h3>

A canonical example of recursion is the computation of Fibonacci numbers:<p>
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 ...
<p>
This sequence can be defined recursively as follows (F(n) is the n-th Fibonacci
number):
<ul type="disc">
	<li>if n = 0, F(n)= 0</li>
	<li>if n = 1, F(n) = 1</li>
	<li>otherwise, F(n) = F(n - 1) + F(n - 2)</li>
</ul>
You can easily follow this definition and generate some Fibonacci numbers for yourself - you
will get precisely the sequence given above.
<p>
How would we generate this sequence in code ? It's quite simple - recursive definitions
are easily reflected in recursive function calls. Here is the C++ code that returns any
Fibonacci number (confined by execution-time and limitations of the C++ <i>long</i> type):
<p>
<pre>
<font color="#0000FF">long</font> <font color="#000000">fib_rec</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">index</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">index</font> <font color="#000000">&lt;</font> <font color="#000000">2</font><font color="#000000">)</font>
        <font color="#0000FF">return</font> <font color="#000000">index</font><font color="#000000">;</font>
    <font color="#0000FF">else</font>
        <font color="#0000FF">return</font> <font color="#000000">fib_rec</font><font color="#000000">(</font><font color="#000000">index</font> <font color="#000000">-</font> <font color="#000000">1</font><font color="#000000">)</font> <font color="#000000">+</font> <font color="#000000">fib_rec</font><font color="#000000">(</font><font color="#000000">index</font> <font color="#000000">-</font> <font color="#000000">2</font><font color="#000000">);</font>
<font color="#000000">}</font>
</pre>
Note how gracefully the mathematical definition is translated to the code of <i>fib_rec</i>. This is the beauty
and elegance of recursion. Unfortunately, everything has its price - while often being 
the most natural way to express algorithms, recursion suffers from performance problems. 
<p>
For example, finding the 40th Fibonacci number (which is, by the way, 102,334,155) using this 
routine takes about 4 seconds on my machine. The 42nd number (267,914,296) takes 11 seconds
to compute, and the time grows very quickly (the 45th, which is 1,134,903,170, takes 47 seconds, etc.)
<p>
One reason for this is the cost of function calls (of which there are many in the recursive
solution). When a function is called, usually some
arguments are pushed on stack, registers are saved, etc. It all takes time, and can hit
the performance of small functions (where the amount of instructions executed for the call
itself is comparable with the amount of instructions needed to perform the function's task).
<p>
This, however, is not the main reason for recursion being slow for the computation of 
Fibonacci numbers. The principal cause in this case is the vast amount of repetition involved.
To demonstrate this, lets try to trace a sample execution of the recursive computation <i>fib_rec</i>, 
taking a call with <i>index </i>set to 5 as an example:
<pre>
fib_rec(5)
|
|---fib_rec(4)
|   |
|   |---fib_rec(3)
|   |   |
|   |   |---fib_rec(2)
|   |   |   |
|   |   |   |---fib_rec(1)
|   |   |   |---fib_rec(0)
|   |   |   
|   |   |---fib_rec(1)
|   |
|   |---fib_rec(2)
|       |
|       |---fib_rec(1)
|       |---fib_rec(0)
|
|---fib_rec(3)
    |
    |   fib_rec(2)
    |   |
    |   |---fib_rec(1)
    |   |---fib_rec(0)
    |
    |---fib_rec(1)
</pre> 
When <i>fib_rec(5)</i> is called, it calls <i>fib_rec</i> with 4 and <i>fib_rec</i> with 3. Each of 
those makes the appropriate calls, et cetera. What you see above is the complete call tree that 
results from the <i>fib_rec(5)</i>. You can generate it yourself by inserting a tracing printout
in the beginning of the function.
<p>
Now, do you notice anything funny about this call tree ? It shouldn't be hard to spot the scandalous 
number of times the same calls are made. For instance, the call <i>fib_rec(1)</i> is made 5 times. The
result of <i>fib_rec(i)</i> surely doesn't change between calls (the first Fibonacci number is, by
definition, 1), so why is there a need for so much repetition ? This, in fact, is the reason for 
the unfortunate inefficiency of recursive algorithms for many computations. So can we really write
nice recursive algorithms and not be daunted by their performance problems ? The answer to this question
if fortunately positive !

<h3>Memoized Fibonacci</h3>

Memoization literally means "putting into memory". An alternative name for it is <i>caching</i>. Caching
is familiar from the hardware world, where a cache is that small amount of fast but expensive memory where
the CPU keeps recent data from the RAM (which is considerably slower than cache), thus avoiding some
costly RAM accesses and saving execution time.
<p>
In programming, Memoization plays a role similar to a hardware cache. It is a technique used to speed up
computer programs by saving intermediary answers for later use, rather than recomputing them. If you look 
at the call tree for <i>fib_rec(5)</i>, you can see that many (most !) of the calls may be avoided by
saving their results in earlier calls. In fact, there's no real need to compute the Fibonacci number
at any index more than once, so five <i>fib_rec</i> calls would do for <i>fib_rec(5)</i>, and not 15
as it currently is.
<p>
So what should we do in order to memoize the Fibonacci computation ? First, we should set up some data 
structure to serve as a cache of computations. Then, when being asked to compute a Fibonacci number
we should first consult the cache. If the result is in cache, it can be returned without any further
computations. If it isn't in the cache - it means we haven't computed it yet, so we compute it and 
add it to the cache. Lets see how this is translated to code:
<pre>
<font color="#0000FF">long</font> <font color="#000000">fib_memoized_aux</font><font color="#000000">(</font><font color="#000000">vector</font><font color="#000000">&lt;</font><font color="#0000FF">long</font><font color="#000000">&gt;&amp;</font> <font color="#000000">cache</font><font color="#000000">,</font> <font color="#0000FF">long</font> <font color="#000000">index</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">index</font><font color="#000000">]</font> <font color="#000000">&gt;=</font> <font color="#000000">0</font><font color="#000000">)</font>
	<font color="#0000FF">return</font> <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">index</font><font color="#000000">];</font>

    <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">index</font><font color="#000000">]</font> <font color="#000000">=</font> <font color="#000000">fib_memoized_aux</font><font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">,</font> <font color="#000000">index</font> <font color="#000000">-</font> <font color="#000000">1</font><font color="#000000">)</font> <font color="#000000">+</font> <font color="#000000">fib_memoized_aux</font><font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">,</font> <font color="#000000">index</font> <font color="#000000">-</font> <font color="#000000">2</font><font color="#000000">);</font>
    <font color="#0000FF">return</font> <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">index</font><font color="#000000">];</font>
<font color="#000000">}</font>


<font color="#0000FF">long</font> <font color="#000000">fib_memoized</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">index</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#000000">vector</font><font color="#000000">&lt;</font><font color="#0000FF">long</font><font color="#000000">&gt;</font> <font color="#000000">cache</font><font color="#000000">(</font><font color="#000000">index</font> <font color="#000000">+</font> <font color="#000000">1</font><font color="#000000">,</font> <font color="#000000">-</font><font color="#000000">1</font><font color="#000000">);</font>
    <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">0</font><font color="#000000">]</font> <font color="#000000">=</font> <font color="#000000">0</font><font color="#000000">;</font>
    <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">1</font><font color="#000000">]</font> <font color="#000000">=</font> <font color="#000000">1</font><font color="#000000">;</font>
    
    <font color="#0000FF">return</font> <font color="#000000">fib_memoized_aux</font><font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">,</font> <font color="#000000">index</font><font color="#000000">);</font>
<font color="#000000">}</font>
</pre>
Here, <i>fib_memoized</i> acts exactly as the simple <i>fib_rec</i> - it takes an index as an argument
and returns the Fibonacci number at this index. Internally, it first sets up a cache (for such a simple
task a vector is enough - the <i>i</i>th vector cell holds the computed <i>i</i>th Fibonacci number, with
-1 meaning a yet-uncomputed result), and uses <i>fib_memoized_aux</i> as a helper function for the 
computations. In <i>fib_memoized_aux</i>, you can see memoization in action, just as described above.
<p>
What about performance, then ? 
<p>
While up to about 30, <i>fib_rec</i> and <i>fib_rec_memoized</i> are
comparable in execution time, afterwards the difference is staggering. For example, computing the 
47th Fibonacci number takes ~47 seconds with <i>fib_rec</i>. With <i>fib_rec_memoized</i> it takes 0
(below resolution of system clock). There's no doubt that the difference gets bigger and bigger
after that.
<p>
There's another major speed-improvement here, which may not be immediately obvious. Imagine that during
the runtime of our program, we need to calculate Fibonacci numbers not just once, but many times. 
While using the plain method we'd go through the computations again and again, using memoization
we can just reuse the cache from call to call. Chances are that most of the 
computations will be answered in constant time - because the result will already be in the cache ! 
<p>
<font size="-1">The assiduous reader may implement a simple class for Fibonacci number calculation. This class will have
the cache as a member, that will be initialized only once. The Fibonacci calculation method will 
use this cache and update it at times (when yet un-calculated results are requested).
</font><p>

<h3>Alternative Fibonacci implementations</h3>

Personally, I don't feel good about the Fibonacci calculation example. Though it's educationally
sound, I find it a little bit contrived. This is because there are fast implementations for 
Fibonacci calculations that don't require memoization (being fast enough anyway). For example,
it's very easy to come up with a simple iterative solution. Since a Fibonacci number is simply a sum
of the previous two, we can use a loop an keep track of just two numbers to generate
any Fibonacci:
<pre>
<font color="#0000FF">long</font> <font color="#000000">fib_iter</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">index</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">index</font> <font color="#000000">&lt;</font> <font color="#000000">2</font><font color="#000000">)</font>
	<font color="#0000FF">return</font> <font color="#000000">index</font><font color="#000000">;</font>

    <font color="#0000FF">long</font> <font color="#000000">cur</font> <font color="#000000">=</font> <font color="#000000">1</font><font color="#000000">;</font>
    <font color="#0000FF">long</font> <font color="#000000">one_back</font> <font color="#000000">=</font> <font color="#000000">0</font><font color="#000000">;</font>

    <font color="#0000FF">for</font> <font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">i</font> <font color="#000000">=</font> <font color="#000000">2</font><font color="#000000">;</font> <font color="#000000">i</font> <font color="#000000">&lt;=</font> <font color="#000000">index</font><font color="#000000">;</font> <font color="#000000">++</font><font color="#000000">i</font><font color="#000000">)</font>
    <font color="#000000">{</font>
	<font color="#0000FF">long</font> <font color="#000000">temp</font> <font color="#000000">=</font> <font color="#000000">cur</font><font color="#000000">;</font>
	<font color="#000000">cur</font> <font color="#000000">=</font> <font color="#000000">cur</font> <font color="#000000">+</font> <font color="#000000">one_back</font><font color="#000000">;</font>
	<font color="#000000">one_back</font> <font color="#000000">=</font> <font color="#000000">temp</font><font color="#000000">;</font>
    <font color="#000000">}</font>

    <font color="#0000FF">return</font> <font color="#000000">cur</font><font color="#000000">;</font>
<font color="#000000">}</font>
</pre>
This will calculate Fibonacci numbers as fast as the memoized implementation - in linear time. <br>
An even faster solution can utilize <i>Binet's Fibonacci number formula</i>:
<pre>
<font color="#0000FF">long</font> <font color="#000000">fib_binet</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">index</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">double</font> <font color="#000000">sqrt_5</font> <font color="#000000">=</font> <font color="#000000">2</font><font color="#000000">.</font><font color="#000000">2360679774997896964091736687313</font><font color="#000000">;</font>

    <font color="#0000FF">return</font> <font color="#000000">(</font><font color="#0000FF">long</font><font color="#000000">)</font> <font color="#000000">floor</font><font color="#000000">((</font><font color="#000000">pow</font><font color="#000000">(</font><font color="#000000">1</font> <font color="#000000">+</font> <font color="#000000">sqrt_5</font><font color="#000000">,</font> <font color="#000000">index</font><font color="#000000">)</font> <font color="#000000">-</font> <font color="#000000">pow</font><font color="#000000">(</font><font color="#000000">1</font> <font color="#000000">-</font> <font color="#000000">sqrt_5</font><font color="#000000">,</font> <font color="#000000">index</font><font color="#000000">))</font> <font color="#000000">/</font>
			<font color="#000000">(</font><font color="#000000">pow</font><font color="#000000">(</font><font color="#000000">2</font><font color="#000000">,</font> <font color="#000000">index</font><font color="#000000">)</font> <font color="#000000">*</font> <font color="#000000">sqrt_5</font><font color="#000000">));</font>
<font color="#000000">}</font>
</pre>
Don't just sit there and gasp in horror :-) Calculation of Fibonacci numbers is a fascinating 
topic and you can learn a lot by browsing the web a little - start by googling "Fibonacci numbers".
<p>
I must note, just to be fair, that these fast non-recursive implementations lack the caching-between-calls
property of memoization. That is, if we use memoization to save results between function calls (discussed
in the last paragraph of the previous section), we can get most results at
a cost of a trivial array look up - faster than the non-recursive implementations.
<p>
But to be even more fair, huge Fibonacci numbers are rarely needed in practice, and even when they
are, the iterative or the formula implementations can provide us with as big numbers as we'll even
need in negligible time. So lets examine another problem, where there is no simple alternative
to the recursive solution.

<h3>Counting change</h3>

As we saw, it isn't hard to come up with a simple iterative Fibonacci algorithm (the same goes for
the factorial function, another common example of recursion in programming books and tutorials). 
<p>
In contrast, consider the following problem:
How many different ways can we make change of $1.00, given half-dollars, quarters ($0.25), dimes ($0.10), 
nickels ($0.05), and cents ($0.01) ? More generally, can we design an algorithm to compute the number
of ways to change any given amount of money ?
<p>
<font size="-1">While at first sight an innocuous problem that might interest supermarket cashiers, this is 
a close relative of an important algorithm - <i>the subset sum problem</i> (once again,
google can be your guide to enlightment).
</font>
<p>
Lets start with an example, to make sure that the problem is understood. In how many ways can be 
make change of 10 cents ? One is 10 times a cent. Two is 
one nickel and five cents. Three is two nickels. Four is a dime. So, four ways.
<p>
In fact, this problem has a simple solution as a recursive procedure. Suppose we think of the types of 
coins available as arranged in some order. Then the following relation holds:
The number of ways to change amount <i>a</i> using <i>n</i> kinds of coins equals
<ul>
<li>the number of ways to change amount <i>a</i> using all but the first kind of coin, plus
<li>the number of ways to change amount <i>a - d</i> using all <i>n</i> kinds of coins, where <i>d</i> is
the denomination of the first coin.
</ul>
<p>
Rationale: note that given a task to make change, we can divide it to two complementary groups:
ways that don't use the first kind of coin, and ways that do. The total number of ways is
the sum of those two groups - that is, the number of ways to make change without using the
first kind of coin, plus the number of ways to make change assuming that we do use the
first kind of coin. But if we've used the first kind, what remains is the amount minus the 
denomination of the first kind.
<p>
Thus, we've found a way to solve the problem by reducing it to two smaller problems (in the 
first the amount of coins is smaller, and in the second the sum is smaller). This is just what 
recursion is about - reducing problems to simpler problems. What we're lacking is an explicit
solution for the "simplest" problems:
<p>
<ul>
<li>If the amount <i>a</i> is 0, there's only one way to make change (no coins)
<li>If the amount <i>a</i> is negative, there is no way to make change
<li>If <i>n</i> is 0, there's only one way to make change (we don't have any choice...)
</ul>
<p>
To convince you that the reduction and boundary cases work, lets look again at the 10 cent
problem (note that we're not interested in 25 and 50 cent coins in this case): So, to change 10 
using the coins 10, 5 and 1 (ordered thus) we
sum (1) the number of ways to change 10 using all but the first kind of coin, that is
using 5 and 1 only, and (2) the number of ways to change amount 10 - 10 = 0 using all kinds of
coins. (2) is simple - there's one way to change amount 0 (by the first boundary case). (1)
can be further reduced to (3) the number of ways to change amount 10 using 1 cent only, plus
(4) the number of ways to change 10 - 5 = 5 using all kinds of coins. (3) is only one way, ten 1 cent
coins, (4) can be reduced, etc. (we get two ways from (4) - one five cent coin, and five one cent
coins). When the algorithm finishes we'll end up with 4 ways.
<p>
To take care of the coins ordering, we'll define a helper function:
<pre>
<font color="#0000FF">long</font> <font color="#000000">first_denomination</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">n_kinds_of_coins</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">switch</font> <font color="#000000">(</font><font color="#000000">n_kinds_of_coins</font><font color="#000000">)</font>
    <font color="#000000">{</font>
	<font color="#0000FF">case</font> <font color="#000000">5</font><font color="#000000">:</font> <font color="#0000FF">return</font> <font color="#000000">50</font><font color="#000000">;</font>
	<font color="#0000FF">case</font> <font color="#000000">4</font><font color="#000000">:</font> <font color="#0000FF">return</font> <font color="#000000">25</font><font color="#000000">;</font>
	<font color="#0000FF">case</font> <font color="#000000">3</font><font color="#000000">:</font> <font color="#0000FF">return</font> <font color="#000000">10</font><font color="#000000">;</font>
	<font color="#0000FF">case</font> <font color="#000000">2</font><font color="#000000">:</font> <font color="#0000FF">return</font> <font color="#000000">5</font><font color="#000000">;</font>
	<font color="#0000FF">case</font> <font color="#000000">1</font><font color="#000000">:</font> <font color="#0000FF">return</font> <font color="#000000">1</font><font color="#000000">;</font>

	<font color="#000000">default</font><font color="#000000">:</font> <font color="#000000">assert</font><font color="#000000">(</font><font color="#000000">0</font><font color="#000000">);</font>
    <font color="#000000">}</font>
<font color="#000000">}</font></pre>
Given how many coins we can use, this function returns the denomination of the first coin. It  
sets up the following ordering of the coins - 50, then 25, then 10, then 5, then 1. 
<p>
Now we're ready for to implement the change counting procedure itself. As a true recursive algorithm, 
it translates into code very naturally:
<pre>
<font color="#0000FF">long</font> <font color="#000000">count_change_aux</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">amount</font><font color="#000000">,</font> <font color="#0000FF">long</font> <font color="#000000">n_kinds_of_coins</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">amount</font> <font color="#000000">==</font> <font color="#000000">0</font><font color="#000000">)</font>
	<font color="#0000FF">return</font> <font color="#000000">1</font><font color="#000000">;</font>
    <font color="#0000FF">else</font> <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">amount</font> <font color="#000000">&lt;</font> <font color="#000000">0</font> <font color="#000000">||</font> <font color="#000000">n_kinds_of_coins</font> <font color="#000000">==</font> <font color="#000000">0</font><font color="#000000">)</font>
	<font color="#0000FF">return</font> <font color="#000000">0</font><font color="#000000">;</font>
    <font color="#0000FF">else</font>
    <font color="#000000">{</font>
	<font color="#0000FF">return</font>
	    <font color="#000000">count_change_aux</font><font color="#000000">(</font><font color="#000000">amount</font><font color="#000000">,</font> <font color="#000000">n_kinds_of_coins</font> <font color="#000000">-</font> <font color="#000000">1</font><font color="#000000">)</font> <font color="#000000">+</font>
	    <font color="#000000">count_change_aux</font><font color="#000000">(</font><font color="#000000">amount</font> <font color="#000000">-</font> <font color="#000000">first_denomination</font><font color="#000000">(</font><font color="#000000">n_kinds_of_coins</font><font color="#000000">),</font> <font color="#000000">n_kinds_of_coins</font><font color="#000000">);</font>
    <font color="#000000">}</font>
<font color="#000000">}</font>


<font color="#0000FF">long</font> <font color="#000000">count_change</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">amount</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#0000FF">return</font> <font color="#000000">count_change_aux</font><font color="#000000">(</font><font color="#000000">amount</font><font color="#000000">,</font> <font color="#000000">5</font><font color="#000000">);</font>
<font color="#000000">}</font>
</pre>
<i>count_change</i> is the procedure that is to be called to get an answer, and it uses 
<i>count_change_aux</i> as a helper function. If you understood the algorithm and the boundary
cases, there's really not much left to explain, since the code is just the algorithm "paraphrased" (to
be exact, written in another language - C++ instead of English). On to some benchmarking:
<p>
<i>count_change</i> answers our original question (how many ways are there to make change of a dollar)
in a no-time - below resolution of system clock (the answer is 292, by the way). However, when we 
start raising the stakes the runtime grows quickly. It takes 5 seconds for 1000 cents, 2.5 minutes
for 2000 and the time soars rapidly on and on. Care to throw a guess at the cause of this slowness ?
Right - it's the same problem we had with <i>fib_rec</i> - multiple repetition of the same 
calculations.
<p>
To get some intuition of the problem, suppose that we run <i>count_change</i> on 2000 cents. Consider
an intermediate sum of 1000 cents. How many ways are there to reach 1000 cents from 2000 cents ? Quite
a lot... But each time we reach 1000 cents we go on and compute the ways to change 1000 cents, and 
we saw that it takes 5 seconds each time - so it's not surprising that the runtime grows so quickly.
<p>
Contrary to the Fibonacci problem, here we don't have any simple way to formulate a swift 
iterative algorithm that will complete the same task (if you find one, let me know !). But 
we'd still like to compute change for large sums in a reasonable time. The solution is
memoization.

<h3>Memoized change counting</h3>

We will proceed in a manner similar to the memoization of <i>fib_rec</i>: we'd like to keep
the results of <i>count_change_aux</i> computations in some cache and return immediately
with a cached result when requested to do some computation for the second time.
<p>
The only slightly problematic point is that we can't just use a simple array for the cache
as we did in <i>fib_memoized</i>, since <i>count_change_aux</i> takes two arguments. But
there's really no problem expanding the memoization technique for two amount of arguments,
as the code demonstrates:
<pre>
<font color="#0000FF">long</font> <font color="#000000">count_change_memoized_aux</font><font color="#000000">(</font><font color="#000000">map</font><font color="#000000">&lt;</font><font color="#000000">pair</font><font color="#000000">&lt;</font><font color="#0000FF">long</font><font color="#000000">,</font> <font color="#0000FF">long</font><font color="#000000">&gt;,</font> <font color="#0000FF">long</font><font color="#000000">&gt;&amp;</font> <font color="#000000">cache</font><font color="#000000">,</font> <font color="#0000FF">long</font> <font color="#000000">amount</font><font color="#000000">,</font> <font color="#0000FF">long</font> <font color="#000000">n_kinds_of_coins</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#000000">pair</font><font color="#000000">&lt;</font><font color="#0000FF">long</font><font color="#000000">,</font> <font color="#0000FF">long</font><font color="#000000">&gt;</font> <font color="#000000">entry</font> <font color="#000000">=</font> <font color="#000000">make_pair</font><font color="#000000">(</font><font color="#000000">amount</font><font color="#000000">,</font> <font color="#000000">n_kinds_of_coins</font><font color="#000000">);</font>
    
    <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">.</font><font color="#000000">find</font><font color="#000000">(</font><font color="#000000">entry</font><font color="#000000">)</font> <font color="#000000">!=</font> <font color="#000000">cache</font><font color="#000000">.</font><font color="#000000">end</font><font color="#000000">())</font>
	<font color="#0000FF">return</font> <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">entry</font><font color="#000000">];</font>

    <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">amount</font> <font color="#000000">==</font> <font color="#000000">0</font><font color="#000000">)</font>
	<font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">entry</font><font color="#000000">]</font> <font color="#000000">=</font> <font color="#000000">1</font><font color="#000000">;</font>
    <font color="#0000FF">else</font> <font color="#0000FF">if</font> <font color="#000000">(</font><font color="#000000">amount</font> <font color="#000000">&lt;</font> <font color="#000000">0</font> <font color="#000000">||</font> <font color="#000000">n_kinds_of_coins</font> <font color="#000000">==</font> <font color="#000000">0</font><font color="#000000">)</font>
	<font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">entry</font><font color="#000000">]</font> <font color="#000000">=</font> <font color="#000000">0</font><font color="#000000">;</font>
    <font color="#0000FF">else</font>
    <font color="#000000">{</font>
	<font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">entry</font><font color="#000000">]</font> <font color="#000000">=</font>
	    <font color="#000000">count_change_memoized_aux</font><font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">,</font> <font color="#000000">amount</font><font color="#000000">,</font> <font color="#000000">n_kinds_of_coins</font> <font color="#000000">-</font> <font color="#000000">1</font><font color="#000000">)</font> <font color="#000000">+</font>
	    <font color="#000000">count_change_memoized_aux</font><font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">,</font> <font color="#000000">amount</font> <font color="#000000">-</font> <font color="#000000">first_denomination</font><font color="#000000">(</font><font color="#000000">n_kinds_of_coins</font><font color="#000000">),</font> 
				      <font color="#000000">n_kinds_of_coins</font><font color="#000000">);</font>
	    
    <font color="#000000">}</font>

    <font color="#0000FF">return</font> <font color="#000000">cache</font><font color="#000000">[</font><font color="#000000">entry</font><font color="#000000">];</font>
<font color="#000000">}</font>


<font color="#0000FF">long</font> <font color="#000000">count_change_memoized</font><font color="#000000">(</font><font color="#0000FF">long</font> <font color="#000000">amount</font><font color="#000000">)</font>
<font color="#000000">{</font>
    <font color="#000000">map</font><font color="#000000">&lt;</font><font color="#000000">pair</font><font color="#000000">&lt;</font><font color="#0000FF">long</font><font color="#000000">,</font> <font color="#0000FF">long</font><font color="#000000">&gt;,</font> <font color="#0000FF">long</font><font color="#000000">&gt;</font> <font color="#000000">cache</font><font color="#000000">;</font>

    <font color="#0000FF">return</font> <font color="#000000">count_change_memoized_aux</font><font color="#000000">(</font><font color="#000000">cache</font><font color="#000000">,</font> <font color="#000000">amount</font><font color="#000000">,</font> <font color="#000000">5</font><font color="#000000">);</font>
<font color="#000000">}</font>
</pre>
<font size="-1">Note that <i>first_denomination</i> remains the same as in the simple recursive version,
so I didn't reproduce it here.</font><p>

Here I use a <i>map</i> as the cache. It maps argument pairs to results: for a pair 
of (amount, n kinds of coins) the cache holds the number of ways to change this amount with
this number of kinds of coins. Except for the different data structure used as a cache,
the changes are very similar to the ones in <i>fib_memoized</i> - first of all the cache
is consulted and if the desired result is already there it's simply returned. Then, the 
real calculation is performed and added to the cache. The next time the function runs with
the same arguments - the computation will be immediaty - simply a fetch from the cache.
<p> 
And indeed, benchmarking shows considerable speed improvement. Change from 2000 cents now takes only 0.02
seconds to compute (vs. 2.5 minutes for the non-memoized version). Change from 5000 takes 0.06
seconds (I gave up waiting for the non-memoized verson to finish this calculations) - the 
runtime increase is linear with the size of the problem - as expected.

<h3>Wrapping up</h3>

In this article you've been introduced to <i>memoization</i> - an important programming technique used
to speed up computations. In particular, memoization often allows one to considerably improve the runtime 
of a crawling recursive algorithm that may be just the right solution for a problem but is too slow to
use. You learned about the inherent slowness in some recursive computations due to repetitions, and 
saw how to use memoization to eliminate this problem.
<p>
You probably noticed the similarity between memoizing the Fibonacci implementation and memoizing
the change counting algorithm. Indeed, memoization is quite simple to apply automatically, if the
programming language allows it. For example, in Lisp where functions are data just like any other
data, memoizing an arbitrary function is trivial. In Perl it is a little bit more tricky, but there
exists an excellent module called Memoize that will automatically memoize any function for you.
As far as I know there is no simple way to achieve this in C++. 

</body>
</html>